1. Field of the Invention
The present invention relates to a path pair designing method and a path pair designing device to create two pieces of disjoint communication paths that do not pass through a same node or a same link on a network, and to a program for causing a computer to execute a path pair designing method.
The present application claims priority of Japanese Patent Application No.2001-165037 filed on May 31,2001, which is hereby incorporated by reference.
2. Description of the Related Art
When specified communication paths are to be created in a network to which a plurality of nodes are connected through links serving as a transmission line, as a typical method of designing the communication path, a “Dijkstra” method (for example, as disclosed in “Optimization Handbook” translated by Masao Iri, Hiroshi Imano, Kaoru Tone, 1995, Asakura Publishing Co., Ltd.) is known.
The Dijkstra method is a way to find out a path having a minimum metric between an entrance node used to guide a packet or a like into a network and an exit node used to guide the packet or the like outside the network. The metric is an index used when a path is found on a network and, as the metric, for example, a number of hops (number of nodes through which a packet or a like passes), delay time, bandwidth, costs or a like are used.
Conventionally, when two disjoint communication paths (hereinafter referred to as a “path pair”) which do not pass through a same node or a same link are created so as to have redundancy, one path (communication path) is designed first by using the Dijkstra method and then another path is designed, after excluding the node or link that has been already used in designing the above one path, again using by the Dijkstra method.
One concrete example of a method of designing the path pair on a network by using the Dijkstra method described above will be explained below by referring to FIG. 4. FIG. 4 is a schematic block diagram illustrating one example of a communication path created by the conventional path pair designing method.
As shown in FIG. 4, a path pair is designed between an entrance node n1 to an exit node n8, for example, on a network having eight pieces of nodes n1 to n8 each being connected by each of links. Moreover, each of the links is expressed as “(na, nb)” (a and b are positive numbers). For example, a link to connect the node n1 to the node n2 is expressed as “(n1, n2)”. Each of the links, shown in FIG. 4, to establish connection among the links is provided with both an upward transmission line and a downward transmission line. For example, each of the links (n1, n2) has both a transmission line to transmit a packet or a like from the node n1 to the node n2 and a transmission line to transmit a packet or a like from the node n2 to the node n1. Moreover, a value indicated by an italicized letter represents a metric value of each of the links. In the example shown in FIG. 4, the metric value for all the links is 1.0. In FIG. 4, only one link between the nodes is shown, however, a plurality of links may be connected between the nodes.
When a path pair is to be created between the entrance node n1 to the exit node n8 in such the network as described above, in the conventional method of designing the path pair, first by using the Dijkstra method, a path is created so that it has a minimum metric value between the node n1 to the node n8. In the example, since the metric value of all links is 1.0, as a path that can provide a minimum metric value between the entrance node n1 to the exit node n8, a path p1 as shown in FIG. 4 is available.
Then, to create a disjoint path not using a same node or a same link as is used for the path pl, all of node n3, node n6, link (n1, n3), link (n3, n6), and link (n6, n8) are removed. However, if so, other paths to transmit a packet or a like from the entrance node n1 to the exit node n8 can not be created.
However, as is apparent from FIG. 4, it is possible to create two paths, one using the node n1-node n2-node n4-node n6-node n8 and another using the node n1-node n3-node n5-node n7-node n8. That is, the network shown in FIG. 4 is so constructed as to create a disjoint path pair.
Therefore, even if a network is so constructed in such a manner to allow a path pair to be created, it is nevertheless impossible to create the path pair so long as the conventional method of designing the path pair is employed in some cases.
Moreover, if the conventional method of designing the path pair is employed, since only such a path as has metric values being in specified order can be selected, for example, a path having a minimum value and a path having a second smallest metric value can be selected, such processing as allows a path pair being a disjoint path pair and the path pair having a smallest path to be selected can not be performed.